package com.lun.hard;

public class SudokuSolver {
	
	//方法一：回溯算法
	public void solveSudoku(char[][] board) {
		backtracking(board);
	}

	private boolean backtracking(char[][] board) {
		
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				if (board[i][j] != '.')
					continue;
				
				for (char k = '1'; k <= '9'; k++) {
					if (isValid(board, i, j, k)) {
						board[i][j] = k;
						if (backtracking(board))//
							return true;
						board[i][j] = '.';
					}
				}
				return false;
			}
		}
		
		return true;
	}

	//方法二：回溯另一写法
	public void solveSudoku2(char[][] board) {
		backtracking2(board, 0, 0);
	}

	private boolean backtracking2(char[][] board, int i, int j) {
		if (i == 9)
			return true;
		if (j == 9)
			return backtracking2(board, i + 1, 0);
		if (board[i][j] != '.')
			return backtracking2(board, i, j + 1);

		for (char c = '1'; c <= '9'; c++) {//
			if (isValid(board, i, j, c)) {
				board[i][j] = c;
				if (backtracking2(board, i, j + 1))
					return true;
				board[i][j] = '.';
			}
		}

		return false;
	}

	private boolean isValid(char[][] board, int row, int col, int num) {
		// 所在行
		for (int i = 0; i < 9; i++) {
			if (board[row][i] == num)
				return false;
		}

		// 所在列
		for (int i = 0; i < 9; i++) {
			if (board[i][col] == num)
				return false;
		}

		// 所属9格
		int startX = row / 3 * 3;
		int startY = col / 3 * 3;

		for (int i = startX; i < startX + 3; i++) {
			for (int j = startY; j < startY + 3; j++) {
				if (board[i][j] == num) {
					return false;
				}
			}
		}

		return true;
	}
}
